A content addressable memory (CAM) is a memory device that permits rapid parallel searching of stored data to find a particular data value. In contrast to most other memory formats (such as ROM and RAM memory), which are based on address-driven storage architectures, the typical CAM memory device offers both address-driven and content-driven data access.
Address-driven memory device architectures are well-known. According to an address-driven architecture, during a memory access, a user supplies an address and stores data, or retrieves data previously stored, at that specific address. For example, in an address-driven architecture, data values may be stored at a particular logical address by specifying the address on an address bus, and supplying data on a data bus to be stored at the specified address. In the same fashion, data may be retrieved on the data bus in response to a memory address supplied on the address bus.
As noted, the typical CAM memory device can be accessed in both address-driven and content-driven fashion. Storage of data in a CAM may be performed in an address-driven mode, as described above. Additionally, some CAM memory devices allow storage of data in a “first available storage location.” For example a logical flag may be provided for each storage location of the CAM device, indicating whether a storage location contains stored data, or is available to receive new data. When a new data item is presented to the CAM device, each logical flag of the logical flag set is tested simultaneously and an unused storage location is identified. The new data item is then stored in the unused storage location, and the logical flag associated with that location is reconfigured to indicate that the location is in use.
As with data storage, data retrieval in a CAM memory may be performed on an address-driven basis. More importantly, however, CAM memory provides content-driven data retrieval. In a content-driven data retrieval, a data pattern is presented to the CAM memory device. If the CAM memory device contains a previously stored data item of the same data pattern, that presence is indicated and the location in the CAM where the searched data is stored is identified and an address connected with the matched data is returned. The CAM memory device is structured to perform the search on a highly parallel basis, conducting the search on all the data in the CAM substantially simultaneously. Consequently, a CAM can provide search results much more rapidly than an address-driven memory device, in which searches are typically performed serially, one address at a time.
The content-driven data retrieval facility of a CAM memory is typically implemented by providing an array of storage cells connected in an extensive wired-or configuration. This architecture allows a multi-bit data word applied to an input of the CAM device to be compared, substantially simultaneously, with the data words stored in every location of the CAM.
FIG. 1 shows a simplified schematic representation of a CAM memory device 10, as known in the art. The CAM device includes a search register 12 and a plurality of storage words 14. Each storage word 14 includes multiple CAM memory cells 16. The search register 12 includes a corresponding plurality of search register bits 18. The search register 12 is coupled to each of the storage words 14 by a parallel bus 20, so that each cell 16 (for example cell 22) of a storage word 14 is coupled to a corresponding bit (for example 24) of the search register 12. Each storage word is coupled to a corresponding match line 26. The match line 26 exhibits electrical capacitance (represented as lumped capacitance 28) and can be pre-charged to a particular electrical potential by a precharge circuit 30.
As shown at 22 each CAM memory cell 16 of each storage word 14 includes a circuit 34 adapted to switchingly couple a particular match line 27 to ground 32. The circuit includes an input 36 coupled to the data bus 20. The input 36 is coupled to a gate of a transistor 38. Transistor 38 is coupled in series with another transistor 40 between the particular match line 27 and ground 32. Input 36 is also coupled, through an inverter 42, to a gate of another transistor 44. Transistor 44 is coupled in series with another transistor 46 between the particular match line 27 and ground 32. A gate of transistor 46 is coupled to a memory element 50. The memory element 50 controls the gate of transistor 46 according to a binary value D stored within memory element 50. A gate of transistor 40 is coupled to a memory element 48. The memory element 48 controls the gate of transistor 40 according to a binary value equal to the complement of D stored within memory element 48.
If the binary data received at input 36 is not equal to D, then the particular match line 27 is switchingly coupled to ground 32 through either transistor 38 and transistor 40 or transistor 44 and transistor 46. If the binary data received at input 36 is equal to D, then the particular circuit 34 does not ground the particular match line 27. If the data values received at the other respective inputs of the particular storage word 29 all match the corresponding “D” values of the respective memory cells 16 of storage word 29, then the particular match line 27 is not grounded at all. Accordingly, match line 27 remains at a detectably high potential, and a data match between the data values held in the search register 12 and the particular storage word 29 is indicated.
In operation, each match line is charged to a precharge voltage by the action of the precharge circuit 30. A binary value is stored in the search register 12. Corresponding binary values are applied to the storage words 14 over the parallel bus 20. If a bit value in the search register differs from a corresponding bit value in a search word 14, that search word switches to provide an electrical path between the respective match line 26 and ground 32. The capacitance 28 of the match line 26 is thus discharged, indicating, by a resulting low match line voltage, that the value in the storage word 14 does not match the value in the search register 12. If a match line remains high (ungrounded), this indicates that the storage word 14 coupled to that match line 26 contains the same value as that present in the search register 12.
In at least some prior art CAM devices, memory cells are arranged in a plurality of memory blocks on a substrate. Each memory block is connected to a respective dedicated data bus that supplies data to the memory block. Different data can be provided on each dedicated data bus. As a result different data may be searched in different memory blocks at the same time. A device 100 constructed according to this architecture is shown in FIG. 2.
FIG. 2 shows a substrate 201 on which are formed first 202 and second 204 memory blocks. Each memory block includes a plurality of CAM memory cells 16 formed on the substrate. The first memory block 202 has a first data input port 206 coupled to a first search register 208. The second memory block 204 has a second data input port 210 coupled to a second search register 212. The first 208 and second 212 search registers are each coupled to a respective search data bus 215, 217. A first control line 219 is coupled to a first control input 218 of the first memory block 202 and a second control input 222 of the first search register 208. A second control line 221 is coupled to a third control input 220 of the second memory block 204 and to a fourth control input 224 of the second search register 212.
A control circuit 226 is coupled to the control lines 219, 221. The control circuit 226 is adapted to apply respective control signals to the control lines 219, 221, thereby initiating comparisons between the values in the search registers 208, 212 and storage words made up of memory cells 16 within the corresponding memory blocks 202, 204. Because each memory block has its own data bus 219, 221, this arrangement is costly in terms of device complexity and associated manufacturing yields, device real estate, and device energy and thermal budgets.
This costliness is a factor in the economics of CAM applications. Accordingly it is desirable to produce a CAM a memory integrated circuit having an improved data bus architecture.